package datastruct;

import java.util.HashMap;
import java.util.Map;

public class LRUCache2 {
    private int capacity;
    Map<Integer, Entry> map = new HashMap<>();
    Entry head = new Entry(-1, -1, null, null);
    int length = 0;
    public LRUCache2(int capacity){
        this.capacity = capacity;
    }

    public int get(int key){
        Entry entry = map.get(key);
        if (entry == null){
            return -1;
        }
        //调整元素的位置，调整到第一个位置
        moveToHead(entry);
        return entry.value;
    }

    public void put(int key, int value){
        Entry entry = map.get(key);
        //更新
        if (entry != null){
            entry.value = value;
            moveToHead(entry);
            return;
        } else {
            Entry newEntry = new Entry(key, value, null, null);
            if (head.after == null){
                head.after = newEntry;
                head.before = newEntry;
                newEntry.before = head;
                newEntry.after = head;
                map.put(key, newEntry);
                length++;
                return;
            }
            if (length < capacity){
                addToHead(newEntry);
                map.put(key, newEntry);
                length++;
            } else {
                addToHead(newEntry);
                map.put(key, newEntry);
                map.remove(head.before.key);
                Entry tail = head.before.before;
                head.before = tail;
                tail.after = head;

            }
        }
    }


    private void addToHead(Entry ptr){
        ptr.after = head.after;
        head.after.before = ptr;
        head.after = ptr;
        ptr.before = head;
    }

    private void moveToHead(Entry ptr){
        if (ptr.before == head){
            return;
        }
        Entry pre = ptr.before;
        pre.after = ptr.after;
        ptr.after.before = pre;

        ptr.after = head.after;
        ptr.before = head;
        head.after.before = ptr;
        head.after = ptr;

    }

}
class Entry{
    int key;
    int value;
    Entry before;
    Entry after;

    Entry(int key, int value, Entry before,Entry after){
        this.key = key;
        this.value = value;
        this.before = before;
        this.after = after;
    }
}
